# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 16:17:57 2020

@author: Administrator
"""

'''
Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

 
'''

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        '''
        20200919--李运辰
        不太熟悉，多练习
           
           
        pre0 =1    8  15
        pre  =3 6  10  18
        '''
        intervals.sort()
        length = len(intervals)
        if length<=1:
            return intervals
        stack = [intervals[0]]
        
        for i in range(1,length):
            latestart,latesend = stack[-1][0], stack[-1][1]
            curstart,curend = intervals[i][0],intervals[i][1]
            
            if latesend>=curstart:
                stack[-1]=[curstart  if curstart<latestart else latestart,  latesend if latesend>curend else curend]
            else:
                stack.append(intervals[i])
        return stack
        